package leetCode;

/**
 * 11 盛最多水的容器
 * 数组/双指针
 给定一个长度为 n 的整数数组height。有n条垂线，第 i 条线的两个端点是(i, 0)和(i, height[i])。

 找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。

 返回容器可以储存的最大水量。

 说明：你不能倾斜容器。

 示例 1：
 输入：[1,8,6,2,5,4,8,3,7]
 输出：49
 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

 示例 2：
 输入：height = [1,1]
 输出：1
 */
public class ContainerWithMostWater {
    public static void main(String[] args) {
        System.out.println(maxAreaMe2(new int[]{2,3,4,5,18,17,6}));
    }

    //逻辑没问题，但是直接超时了，样本超大，日他爹了
    public static int maxAreaMe(int[] height) {
        int result = 0;
        for (int i =0;i<height.length;i++) {
            int j = i + 1;
            while (j < height.length) {
                int min = Math.min(height[i],height[j]);
                result = Math.max(result,(j - i) * min);
                j++;
            }
        }
        return result;
    }

    //通过，不优雅，67/57
    public static int maxAreaMe2(int[] height) {
        int result = 0;
        int j = height.length - 1;
        for (int i=0;i < height.length;i=i) {
            if (i == j) {
                break;
            }
            result = Math.max(result,(j - i)*(Math.min(height[i],height[j])));
            if (height[i] > height[j]) {
                j--;
            } else {
                i++;
            }
        }
        return result;
    }

    //官方，双指针，就是把我的for换成了while，内存消耗打败了94，速度持平
    public int maxArea(int[] height) {
        int l = 0, r = height.length - 1;
        int ans = 0;
        while (l < r) {
            int area = Math.min(height[l], height[r]) * (r - l);
            ans = Math.max(ans, area);
            if (height[l] <= height[r]) {
                l++;
            }
            else {
                r--;
            }
        }
        return ans;
    }

    //勾八写法，93/82，牛逼，这个for有一手
    public int maxAreaGood(int[] a) {
        int max = 0;
        for(int i = 0, j = a.length - 1; i < j ; ){
            int minHeight = a[i] < a[j] ? a[i ++] : a[j --];
            max = Math.max(max, (j - i + 1) * minHeight);
        }
        return max;
    }
}
